1436E - Complicated Computations - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n;
int a[N],pre[N];
int flag[N];
struct node{
	int l,r,sum;
}b[N*4];
void build(int x,int l,int r){
	b[x].l=l,b[x].r=r;
	if(l==r){
		return ;
	}
	int mid=(l+r)/2;
	build(x*2,l,mid);
	build(x*2+1,mid+1,r);
}
void update(int x,int l,int sum){
	if(b[x].l==b[x].r){
		b[x].sum=sum;
		return ;
	}
	int mid=(b[x].l+b[x].r)/2;
	if(l<=mid){
		update(x*2,l,sum);
	}else{
		update(x*2+1,l,sum);
	}
	b[x].sum=min(b[x*2].sum,b[x*2+1].sum);
}
int Sum(int x,int l,int r){
	if(l<=b[x].l&&b[x].r<=r){
		return b[x].sum;
	}
	int mid=(b[x].l+b[x].r)/2,ans=2147483647;
	if(l<=mid){
		ans=min(ans,Sum(x*2,l,r));
	}
	if(r>mid){
		ans=min(ans,Sum(x*2+1,l,r));
	}
	return ans;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	build(1,1,n+2);
	for(int i=1;i<=n;i++){
		if(a[i]>1){
			flag[1]=1;
			if(Sum(1,1,a[i]-1)>pre[a[i]]){
				flag[a[i]]=1;
			}
		}
		update(1,a[i],i);
		pre[a[i]]=i;
	}
	for(int i=2;i<=n+2;i++){
		if(Sum(1,1,i-1)>pre[i]){
			flag[i]=1;
		}
	}
	for(int i=1;;i++){
		if(!flag[i]){
			printf("%d",i);
			return 0;
		}
	}
	return 0;
}